package com.mlh.doublepointer;


//给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
// 同时还满足 nums[i] + nums[j] + nums[k] == 0 。
// 请你返回所有和为 0 且不重复的三元组。
//注意：答案中不可以包含重复的三元组
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
	public static void main(String[] args) {
		List<List<Integer>> lists = method1(new int[]{-1, 0, 1, 2, -1, -4});
		System.out.println(lists);
	}
	//看题解写出 排序+双指针
	public static List<List<Integer>> method1(int[] nums) {
		List<List<Integer>>res=new ArrayList<>();
		//先对数组进行排序
		Arrays.sort(nums);
		int n=nums.length-1;
		//主要思路 遍历数组 以i位置作为三数的最小者 双指针去寻找另外两数  让三数之和为0
		for(int i=0;i<=n;i++){
			if(nums[i] > 0){//当nums[i]>0 不能凑出nums[i]+nums[left]+nums[right]=0 因此直接返回
				return res;
			};
			//去重操作，确保第一个元素不相同，以此来避免元祖间的重复
			if(i>0&&nums[i-1]==nums[i]){
				continue;
			}
			int left=i+1;
			int right=n;
			while (left<right){
				if(nums[i]+nums[left]+nums[right]>0){
					right--;
				}else if(nums[i]+nums[left]+nums[right]<0){
					left++;
				}else{ //结果=0加入res数组
					ArrayList<Integer> temp = new ArrayList<>();
					temp.add(nums[i]);
					temp.add(nums[right]);
					temp.add(nums[left]);
					res.add(temp);
					//以i位置为最小数 可能还会有其他答案  为了答案不重复
					//要跳过此时与nums[left]  nums[right] 相同的数 去寻找与此答案不同的答案
					while (left<n&&nums[left]==nums[left+1]){
						left++;
					}
					while (right>0&&nums[right]==nums[right-1]){
						right--;
					}
					left++;
					right--;
				}
			}
		}
		return res;
	}
	public static List<List<Integer>> pratices(int[] nums) {
		List<List<Integer>>res=new ArrayList<>();
		Arrays.sort(nums);
		for (int i = 0; i < nums.length; i++) {
			if(nums[i]>0){
				return res;
			}
			if(i>0&&nums[i]==nums[i-1]){
				continue;
			}
			int right=nums.length-1;
			int left=i+1;
			while(right>left){
				if(nums[i]+nums[left]+nums[right]>0){
					right--;
				} else if (nums[i]+nums[left]+nums[right]<0) {
					left++;
				}else{
					res.add(Arrays.asList(nums[i],nums[left],nums[right]));
					while (right>left&&nums[right]==nums[right-1]){
						right--;
					}
					while (right>left&&nums[left]==nums[left+1]){
						left++;
					}
					right--;
					left++;
				}
			}
		}
		return res;
	}

	public static List<List<Integer>> practice2(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>>res=new ArrayList<>();
		for (int i = 0; i < nums.length-2; i++) {
			if(nums[i]>0){
				return res;
			}
			if(i>0&&nums[i]==nums[i-1]){
				continue;
			}
			int left=i+1;
			int right=nums.length-1;
			while(left<right){
				if(nums[left]+nums[right]+nums[i]>0){
					while (left<right&&nums[right]==nums[right-1]){
						--right;
					}
					--right;
				}else if(nums[left]+nums[right]+nums[i]<0){
					while(left<right&&nums[left]==nums[left+1]){
						++left;
					}
					++left;
				}else{
					res.add(Arrays.asList(nums[left],nums[right],nums[i]));
					while(left<right&&nums[left]==nums[left+1]){
						++left;
					}
					while (left<right&&nums[right]==nums[right-1]){
						--right;
					}
					++left;
					--right;
				}
			}
		}
		return res;
	}
}
